[SW Expert Academy] 1907. 모래성 쌓기

Posted on March 30, 2021

문제 :

산골에 있는 삼성초등학교에 다니는 학생들에게 바다란 미지의 영역이다. 여름방학을 맞아 학생들은 바다로 놀러 왔다.

드넓은 백사장과 저 멀리 뻗은 수평선이 학생들을 맞이해 주었다.

학생들은 낮에는 바다에서 신나게 놀았고, 이제 밤이 되어 백사장에서 모래성을 짓고 놀기로 하였다.

계획적인 것을 좋아하는 삼성초등학교 학생들은 2차원 격자단위로 모래성을 만들었는데, 각 격자에 들어있는 모래마다 튼튼함의 정도가 다르다.

튼튼함이란 모래성에 파도가 칠 때 격자에 들어있는 모래가 무너져서 씻겨 나갈지 아닐지를 의미하는데 1에서 9사이의 숫자로 표현되며,

파도가 칠 때 현재 격자의 주변 8방향(상하좌우 대각선)에 모래가 있지 않은 칸의 개수가 현재 칸의 튼튼함보다 많거나 같을 경우 파도에 의해 무너짐을 의미한다.

모래성에 파도가 치면 칠수록 모래성을 깎여 나가고 최종적으로는 하나의 형태로 수렴한다.

과연 몇 번의 파도가 쳐야 모래성의 형태가 더 이상 변하지 않게 될까?

입력 :

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다 모래성의 격자의 크기 H, W(1 ≤ H, W ≤ 1,000)이 공백으로 구분되어 주어진다.

다음 H줄에는 길이가 W인 문자열이 주어진다.

문자열은 ‘.’또는 ‘1’~‘9’로 구성되어 있으며 숫자는 각 칸에 들어 있는 모래의 튼튼함을 의미하고 ‘.’는 모래가 없는 칸임을 의미한다.

격자의 최 외곽부는 모두 ‘.’이다.

출력 :

각 테스트 케이스마다 몇 번의 파도가 쳐야 모래성의 형태가 더 이상 변하지 않게 되는지를 출력한다.

풀이 :

처음에는 단순한 bfs 문제일 줄 알고 덤볐지만… 역시 정답률이 낮은데는 다 이유가 있는 듯 하다.

꽤 많은 시간을 투자해야 했고,,, 결론적으로는 거의 완벽에 가까울 정도로 최적화하지 않으면 테스트 케이스들을 제시간에 해결하기가 힘든 문제였다.

우선 큰 로직은 다음과 같이 설계했다.

모래성이 쌓여있지 않은 부분(’.‘)들을 처음에 큐에 저장해두고 큐에서 하나씩 빼면서 주변에 쌓인 모래성의 높이를 1씩 줄여준다. → 주변 모래성중 0이 되는 곳이 있으면 큐에 넣어준다.
모래성이 쌓여있지 않은 부분들이 큐에서 모두 빠지면(’.’ 부분만 저장 되어있을 때 큐의 사이즈만큼 반복문 돌리기) 그 다음 큐에 쌓여있는 인덱스 정보들은 모두 첫 회차에서 무너진 모래성들이다
여기서부터는 무너진 모래성들의 인덱스에서 주변 8방향을 확인하며 다시 주변 모래성의 value를 1씩 줄여준다.
1번 과정과 마찬가지로 0이 되는 모래성은 큐에 넣어주면서 다음 번에 무너질 모래성 위치를 저장해 준다.
3번 과정부터 다시 재반복하며, 큐에 저장된 정보가 없을 때까지의 반복횟수를 구해주면 답이 된다.

로직은 사실 처음부터 이와 같이 접근했고, 다른 분들의 코드를 참고해보았을 때에도 로직은 거의 비슷한 것을 비교해보면 로직에는 큰 문제가 없어보인다.

하지만 최적화를 시키지 않으면 어김없이 시간 초과가 떳다.

내가 사용한 최적화 방식은 다음과 같다.

처음에는 모래성이 없는 부분을 탐색하는 것이 아닌 모래성의 위치에서 주변 8방향을 탐색하는 방식을 사용했다. 하지만, 이 방법은 정말 끝까지 시간초과 결과가 났다.. 사실 아직까지 이 부분은 왜 모래성이 없는 부분을 탐색해야 시간이 줄어드는지 감이 안온다.. 모래성이 있는 부분이 더 적으면 모래성이 없는 부분을 탐색하는 것 보다 더 시간이 적게 걸리지 않을까.. 라는 의문에 사실 이 부분은 왜 최적화가 되었는지 잘 모르겠다.
또 하나의 최적화 방식은 처음에 모래성의 높이를 줄여주는 방식이 아니라 하나의 배열을 더 만들어 현재 8방향 중 모래성이 없는 부분을 카운트해서 그 값을 저장하는 방식을 사용했다. 하지만 이 방식은 배열을 초기화해주는 것은 물론이고 매번 두개의 배열의 값을 비교하고 굳이 다른 배열의 값을 증가시켜야 되는 부분에서 조금 비효율적인 것 같다. 그래서 해당 map 배열에서 모래성의 높이를 줄이는 방법으로 구현했다.

코드 :

코드 보기/접기

#include<iostream>
#include<cstring>
#include<queue>
#include<utility>
 
#define pii pair<int, int>
 
using namespace std;
int map[1000][1000], origin[1000][1000], n, m;
int di[8] = {0, 1, 1, 1, 0, -1, -1, -1 }, dj[8] = {1, 1, 0, -1, -1, -1, 0, 1};
queue<pii> collapseq;
 
void whoCollapse() {
    int size = collapseq.size();
     
    for(int i=0; i<size; i++) {
        int curx = collapseq.front().first, cury = collapseq.front().second;
        collapseq.pop();
         
        for(int k=0; k<8; k++){
            int cmpx = curx + di[k], cmpy = cury + dj[k];
            if(cmpx < 0 || cmpx >= n || cmpy < 0 || cmpy >= m) continue;
            if(origin[cmpx][cmpy])    
                if(!(--map[cmpx][cmpy]))
                    collapseq.push(pii(cmpx, cmpy));
        }
    }
}
 
void nextCollapse() {
        int size = collapseq.size();
     
    for(int i=0; i<size; i++) {
        int curx = collapseq.front().first, cury = collapseq.front().second;
        collapseq.pop();
         
        for(int k=0; k<8; k++){
            int cmpx = curx + di[k], cmpy = cury + dj[k];
            if(cmpx < 0 || cmpx >= n || cmpy < 0 || cmpy >= m) continue;
            if(map[cmpx][cmpy])    {
                map[cmpx][cmpy]--;
                if(!map[cmpx][cmpy]) collapseq.push(pii(cmpx, cmpy));
            }
        }
    }
}
 
int testCase() {
    char input;
    int answer = 0;
    cin >> n >> m;
     
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++){
            cin >> input;
            if (input == '.') {
                map[i][j] = 0;
                collapseq.push(pii(i, j));
            }
            else
                map[i][j] = input - '0';
            origin[i][j] = map[i][j];
        }
     
    if(collapseq.size()) whoCollapse();
     
    while(collapseq.size()) {
        answer++;
        nextCollapse();
    }
    return answer;
}
 
int main(int argc, char** argv)
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int test_case;
    int T;
    cin>>T;
 
    for(test_case = 1; test_case <= T; ++test_case)
    {
        cout << '#' << test_case << ' ' << testCase() << '\n';
    }
    return 0;
}

Algorithm

algorithm SW Expert C++